1. Field of the Invention
This invention relates to packet radio communication systems. More specifically, it relates to a method for routing packets with increased efficacy in an ad-hoc wireless mesh communications network.
2. Description of the Related Art
A mesh network is a network that employs one of two connection arrangements, full mesh topology or partial mesh topology. In the full mesh topology, each node is connected directly to each of the others. In the partial mesh topology, nodes are connected to only some, not all, of the other nodes. Nothing is necessarily dynamic in a mesh. However, in recent years, and in connection with wireless networks, the term “mesh” is often used as a synonym for “ad hoc” or “mobile” network. Obviously, combining the two characteristics of a mesh topology and ad hoc capabilities is an attractive proposition.
As used herein, a wireless mesh network assumes a network that handles many-to-many connections and is capable of dynamically updating and optimizing these connections. This may be (but does not have to be) a mobile network in which it is assumed that each (or at least some) of the nodes of the network are mobile units that change position over time. The dynamic management of complex routing information, which likely includes information about external networks (e.g. the Internet and gateways to it), is arguably the biggest challenge for (dynamic) mesh protocols.
Mesh Networking is particularly suited to wireless networks, where the connections can't be predicted in the same way as a wired network. Wireless mesh networking is mesh networking implemented over a wireless packet radio. It caters to mobile nodes, instant network growth and unpredictable variations in reception and coverage.
Mesh networking builds up a wide-spread, multi-hop network with each node joining neighboring nodes already in the network on demand. Once joined the nodes can explore the network and establish their routes through it, finding the resources that they need automatically.
Networking infrastructure is therefore decentralized and inexpensive, as each node need only transmit as far as an adjacent node rather than a centralized base station. Nodes act as repeaters to transmit data from nearby nodes to peers that are too far away to reach, resulting in a network that can span a large distance, especially over rough or difficult terrain. Mesh networks are also extremely reliable, as each node is connected to several other nodes. If one node drops out of the network, due to hardware failure or any other reason, its neighbors simply find another route. Extra capacity as permitted by radio spectrum usage can be installed by simply adding more nodes. Mesh networks may involve either fixed or mobile devices.
In packet-routed networks data is broken up into packets having a certain maximum size. A data packet is provided with a header containing information about the packet. This information may include the source of the packet, the intended destination of the packet and where the data in that particular packet fits into the data stream. A data packet hops from one device to another until it reaches a given destination. Dynamic routing capabilities included in each device allow this to happen. Each device must determine what to do with the data it receives—pass it on to the next device, keep it or delete it.
In a wireless network, packets may be transmitted by a radio transmitter and received by a radio receiver (together, a “transceiver”). Most often, such transmissions are omni-directional—i.e., the transmitter broadcasts the signal in all directions and any receiver within range receives it. Upon receiving a data packet, one of the first things a receiver may do is examine the packet's header to determine whether it (the receiving node) is the intended recipient—i.e., whether it is the specified destination of the packet. If so, the packet may be placed into a queue for subsequent re-assembly of the data stream. However, if it is not the intended destination, the receiver must decide what to do with the packet. One simple strategy is simply to ignore it—i.e., “drop” the packet. This strategy limits data transmission to nodes that are directly within the range of a transmitting node.
Another simple strategy is to have the receiving node retransmit the packet if it is not the intended destination and it has not previously retransmitted the packet. This has the equivalent effect of boosting the signal as it travels through nodes acting as repeaters, but the network can quickly become overloaded since it is a naïve, blind retransmission and there is no strategy to limit the life of packets and no “direction” to their travel through the network. Accordingly, a number of more sophisticated algorithms have been developed to address these issues.
In current networks, routing of data is done in a deterministic manner so that information that no longer reflects the topology of the network due to the failure of a part of a network usually negatively impacts the performance of the entire network. Most networks have a large number of stable connections and nodes. In such networks, deterministic algorithms can be used to effectively route data from any point in a network to any other point in the same network. Deterministic algorithms have a certain level of overhead that is only tolerable in stable networks given the performance of the algorithm after such overhead is paid—each node must have knowledge of the topology of the network. However, an increasing number of networks are now appearing where there exists such a low level of connection stability and node availability that the overhead associated with deterministic algorithms, that was acceptable in stable networks, effectively becomes a cost that dominates any benefit afforded by the algorithm. Examples of such less stable networks that Ad-Hoc Mesh Routing (“AHMR”) can be used to address are ad-hoc wireless networks.
Algorithms of the prior art which attempt to form a temporarily stable structure to ad-hoc networks without the use of any existing network infrastructure or centralized components include Ad-hoc On-Demand Distance Vector Routing (AODV), Destination-Sequenced Distance Vector protocol (DSDV), Temporally-Ordered Routing Algorithm (TORA), Associativity Based Routing (ABR) and Dynamic Source Routing (DSR). The AODV and DSDV algorithms are discussed in detail, below.
Most ad-hoc routing algorithms can be divided into one of two categories—table driven algorithms, and source-initiated on-demand driven algorithms. Table driven algorithms are characterized by an attempt to maintain network-wide, consistent, and up-to-date information about the network and the routes from one node to any other node in the network. These algorithms are often associated with a constant propagation of routing information that is routine or triggered by topology changes. This information must be propagated to all nodes, which results in the algorithm incurring substantial amounts of overhead and network traffic. However, because a consistent view is constantly being updated on every node, there is little latency associated with sending initial packets, and routes are always defined. The result of constantly maintaining views of the network topology is accuracy which is a function of the size of the network. However, these algorithms do not scale well, and the level of network overhead increases drastically with the size of the network. Thus, these algorithms have poor scalability characteristics.
Source-initiated on-demand driven algorithms build routes on demand, and when a source node requests. There is no need to maintain a consistent view of global network state on each component node, and as such, there is substantially less overhead necessary. However, there is a cost associated with the first query when a route to a specific destination is requested. Furthermore, this cost is incurred on every query to establish a route, which often occurs in association with a broken route. However, the substantially lower level of network overhead resulting from not having to keep a consistent view of the entire network topology on every node allows this class of algorithms to scale better than Table-Driven algorithms. However, these algorithms scale in proportion to the average length of routes, and as this increases, overhead quickly increases.
Another class of algorithms, in which the method of the present invention exists, are algorithms in which there are few constraints on data propagation and no need for any global state to be maintained. There is no concept of an explicit route as seen in the source-initiated on-demand algorithms, nor is there a need to maintain an accurate and global view of the network state on each individual nodes. Data is allowed to freely flow through the network, and data is directed on a network level reflecting the aggregate behavior of the network.
Ad-hoc On-Demand Distance Vector Routing (AODV)
Ad-hoc On-Demand Distance Vector Routing (hereafter referred to as “AODV”) is a routing algorithm designed for ad-hoc topologically unstable networks that is based on building specific routes between a node and its destination only when requested, or “on-demand”. The routes are then maintained on an “as needed” basis where routes are eliminated upon a timeout based on data traffic or when it is discovered that an intermediate node along the node breaks the chained route. In building routes, AODV also supports the creation of multicast trees in which members are connected by routes.
AODV uses a chained, cyclical sequence of route/request queries in order to first conduct route discovery, and then to inform nodes back along the route of their membership in the specific route. In order to find a route, the source node broadcasts a route request query packet (RREQ). Nodes that receive the RREQ packet then take note of the node sending the RREQ packet to set up a reverse route to that node corresponding to the requested route, and then forwards the RREQ packet onward if it is either not the destination nor does it have the requested route in it's route table. This process continues until the destination or route-to-destination is reached. At this point, a route reply packet (RREP) is returned along the back-pointers constructed during the propagation of the RREQ packet. During traversal of the back-pointers, corresponding pointers pointing toward the destination are set up creating the route of forward pointers. Upon receiving the RREP packet, the source can then send data over the route which now has been constructed with forward and back pointers. All the intermediate nodes keep the route, defined locally as an intermediary's forward and back pointers corresponding to a specific endpoint route, as long as the route is active and has data periodically traversing it. If data does not traverse the links, a timeout occurs on a local level and the route is eliminated from the participating nodes on a local level. Additionally, in the event of a route break, the nodes that discover the break proceed to send a route error (RERR) message back to the source to inform the source of the break. In this case, the source must then reinitiate the route discovery protocol by broadcasting the RREQ packet again.
Destination-Sequenced Distance Vector (DSDV)
Destination-Sequenced Distance Vector routing protocol (hereafter referred to as “DSDV”) is a routing algorithm designed for ad-hoc networks that is based on maintaining on each node, distance information about the appropriate next hop for each reachable destination in the network. DSDV was derived from the conventional Reservation Information Protocol (RIP) and as such, shares most of its functionality with RIP with the addition of a sequence number to distinguish stale routes. Functionality of this algorithm requires each distinctly identified node to periodically broadcast routing updates. Furthermore, this protocol attempts to maintain consistent, up-to-date routing information about the network.
DSDV operates by identifying all available destination nodes with unique even sequence numbers. Each DSDV node also maintains a routing table with an entry for routes to each possible destination. Each node then places a sequence number on each route in the routing table with information regarding the next hop to a certain destination, a cost metric for each hop, and a destination used to identify the correct hop in the node. The sequence numbers are used to uniquely identify routes in order to eliminate loops/cycles in the route. Furthermore, maintenance for this algorithm requires periodic transmitting of node routing tables in order to maintain table consistency on a global basis. These routing table synchronizations take the form of full table sharing, known as full dumps, and smaller synchronizations known as incremental dumps. In the case of full dumps, the packet carries all available routing information. However, the incremental dumps are used to relay differences, or changes, that have changed a local node's table.
Having a global up-to-date view of the network allows each node in the network to know which neighbor to forward data on to in order to move along the most direct route towards the destination.
At the heart of DSDV is the need to create and maintain globally consistent views of the network on each component node. This in turn incurs a level of network overhead that is unacceptable on wireless networks where the link medium is shared and constant broadcasting of table information can quickly saturate a wireless link.
With the increasing prevalence of topologically unstable networks, a new paradigm is needed to handle a constantly changing topology while still providing a similar level of connectivity and throughput that more traditional wired networks possess. Existing algorithms, most of which are deterministic, either impose too great of an overhead on topologically unstable networks in an attempt to maintain comparable levels of connectivity or do not have heavy levels of overhead at the cost of a much lower level of connectivity and throughput than can and should be attainable. In addition, because the topology is unstable, deterministic algorithms face significant challenges in dealing with incomplete, stale or erroneous topology information that simply arises because the network components are mobile. Lastly, most currently implemented algorithms rely on a quasi-centralized method of coordinating variable networks. Using a centralized design, even if designed in a hierarchical manner, creates certain points of failure that reduce the robustness of the overall network to reflect and scale to the number of coordinating nodes rather than the number of nodes comprising the network.